# -*- coding: utf-8 -*-

"""剑指 Offer II 092. 翻转字符
如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
返回使 s 单调递增 的最小翻转次数。

示例 1：
输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：
输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：
输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

提示：
1 <= s.length <= 20000
s 中只包含字符 '0' 和 '1'"""

class Solution:
    """到第i位翻转成单调递增，那么与第i-1位为'0',还是'1'有关，
    所以一个最优解问题可以拆分成第i位为0的最少翻转，第i位为1的最少翻转，再求两者最优解
    动态规划+递归"""
    def minFlipsMonoIncr(self, s: str) -> int:
        memory = dict([(i, {}) for i in range(len(s))])
        memory[0] = {'0': int(s[0])^int('0'), '1': int(s[0])^int('1')}

        def optimal(i, state):
            if i == 0:
                return memory[0][state]
            
            if '0' in memory[i-1]:
                pre_zero = memory[i-1]['0']
            else:
                pre_zero = optimal(i-1, '0')
                memory[i-1]['0'] = pre_zero
            
            if '1' in memory[i-1]:
                pre_one = memory[i-1]['1']
            else:
                pre_one = optimal(i-1, '1')
                memory[i-1]['1'] = pre_one

            if state == '0':
                return pre_zero+(int(s[i])^int('0'))
            else:
                return min(pre_zero, pre_one)+(int(s[i])^int('1'))
        last = len(s)-1
        return min(optimal(last, '0'), optimal(last, '1'))


if __name__ == '__main__':
    so = Solution()
    print(so.minFlipsMonoIncr("00110"))
    print(so.minFlipsMonoIncr("010110"))
    print(so.minFlipsMonoIncr("00011000"))
